package 字节跳动手撕.A;

import java.lang.reflect.Parameter;
import java.security.PublicKey;
import java.util.*;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        this.val = x;
    }

    TreeNode(int x, TreeNode left, TreeNode right) {
        this.val = x;
        this.left = left;
        this.right = right;
    }

    // 判断是否对此  进行遍历 拿到中序遍历的结果 判断是否是回文串即可
    public static boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }

    //left 和right值相等  false 条件有一个为空另一个不为空
    public static boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        // 二叉树的层次遍历方式  使用队列
        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root == null) {
            return new ArrayList<>();
        }
        queue.add(root);
        List<List<Integer>> result = new LinkedList<>();
        boolean flag = true;
        while (!queue.isEmpty()) {
            //双向队列
            Deque<Integer> level = new ArrayDeque<>();
            int size = queue.size();
            //size是当前层数的队列
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                //加一个flag来判断
                if (flag) {
                    level.addLast(cur.val);
                } else {
                    level.addFirst(cur.val);
                }
                //还是左孩子先进来  右边孩子后进来
                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
            result.add(new LinkedList<>(level));
            flag = !flag;
        }
        return result;
    }

    public void flatten(TreeNode root) {
        //以前序遍历的方式 展开二叉树的结构
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null) {
            prev = cur.right;
            if (cur.left != null) {
                // 最后一个节点就是右子树的最后一个节点
                while (prev.right != null) {
                    prev = prev.right;
                }
                prev.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            //prev向前序遍历下面最后一个节点
            //向右移根节点
            cur = cur.right;
        }
    }

    //二叉树的所有路径之和
    public List<String> binaryTreePaths(TreeNode root) {
        //从根节点出来  不断往下走  知道叶子节点
        List<String> list = new ArrayList<>();
        binary(root, list, new StringBuffer());
        return list;
    }

    private static void binary(TreeNode root, List<String> result, StringBuffer str) {
        if (root == null) {
            return;
        }
        StringBuffer res = new StringBuffer(str);
        res.append(root.val);
        if (root.left == null && root.right == null) {
            result.add(res.toString());
        } else {
            res.append("->");
            binary(root.left, result, res);
            binary(root.right, result, res);
        }
    }

    public int maxPathSum(TreeNode root) {
        getMaxValue(root);
        return maxSum;
    }

    int maxSum = Integer.MIN_VALUE;

    private int getMaxValue(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftGain = Math.max(getMaxValue(root.left), 0);

        int rightGain = Math.max(getMaxValue(root.right), 0);

        //最大值  更新最大值
        int pricenew = root.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pricenew);

        //只选择了一条路径
        return root.val + Math.max(leftGain, rightGain);
    }
    //创建一个Pair类 存储节点值和对应的下标索引值
    public int widthOfBinaryTree(TreeNode root) {
       List<Pair> list=new ArrayList<>();
       list.add(new Pair(root,1));
       int maxLen=1;
       while (list.size()>0){
           List<Pair> temp=new ArrayList<>();
           for(Pair pair:list){
               TreeNode node=pair.node;
               Integer index=pair.index;
               if (node.left!=null){
                   temp.add(new Pair(node.left,index*2));
               }
               if (node.right!=null){
                   temp.add(new Pair(node.right,index*2+1));
               }
           }
           maxLen=Math.max(maxLen,list.get(list.size()-1).index-list.get(0).index+1);
           list=temp;
       }
       return maxLen;
    }
    static class Pair{
       public TreeNode  node;
        public  Integer  index;
        public Pair (TreeNode node,Integer index){
            this.node=node;
            this.index=index;
        }
    }

//    public int[] shuffle(int[] nums, int n) {
//    //重新排序数组
//        int index1=0;
//        int index2=n;
//        int a[]=new int[nums.length];
//        for (int i = 0; i <nums.length; i++) {
//            if (i%2==0){
//                a[i]=nums[index1];
//                index1++;
//            }else{
//                a[i]=nums[index2];
//                index2++;
//            }
//        }
//        return a;
//    }

    public int[] shuffle(int[] nums, int n) {
//        int index = 0, mask = (1 << 10) - 1;
//        for (int i = 0; i< < n; i++) {
//            nums[index++] = (nums[i] & mask) << 10 | (nums[index - 1] & mask);
//            nums[index++] = (nums[i + n] & mask) << 10 | (nums[index - 1] & mask);
//        }
//        for (int i = 0; i < 2*n; i++)  nums[i] >>= 10;
//        return nums;
        int  index=0,mask=(1<<10)-1;
        for (int i = 0; i <n ; i++) {
            nums[index++]=(nums[i]&mask)<<10 |(nums[index-1]&mask);

            nums[index++]=(nums[i+n]&mask)<<10 |(nums[index-1]&mask);
        }
        //向右移动十位数字保存值
        for (int i = 0; i < n*2; i++) {
            nums[i]>>=10;
        }
        return nums;
    }
    public int maximumGap(int[] nums) {
       int n=nums.length;
       if (n<=0){
           return 0;
       }
       //计算两个之间的最大值
        Arrays.sort(nums);
       int temp=nums[1]-nums[0];
        for (int i = 1; i <nums.length ; i++) {
            temp=Math.max(nums[i]-nums[i-1],temp);
        }
        return temp;
    }
    public static void main(String[] args) {
        // 5
        System.out.println(getMaxLen("pwwkew"));
    }
    // abcadefa
    public static int   getMaxLen(String str){
        Set<Character> set=new HashSet<>();
        int n=str.length();
        int i=0,j=0;
        int maxLen=0;
        while (i<n){
            char c= str.charAt(i);
            if (set.contains(c)){
                 while (set.contains(c)){
                     set.remove(str.charAt(j));
                     j++;
                 }
            }
            set.add(c);
            i++;
            maxLen=Math.max(maxLen,i-j);
        }
        return maxLen;
    }

    //二叉树的右视图   从右边看整个二叉树的形状

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (queue.size() > 0) {
            int n=queue.size();
            list.add(queue.peek().val);
            while (n-->0){
                TreeNode node = queue.poll();
                if (node.right != null) {
                    queue.add(node.right);
                }
                if (node.left != null) {
                    queue.add(node.left);
                }
            }
        }
        return list;
    }

}
